package com.lenl.arithmetic.tenusablealgorithm.horse;

import java.awt.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

/**
 * @author Lenl
 * @version v1.0
 * @create 2022-05-16 16:19
 * @description 骑士周游问题
 */
public class HorseChessBoard {

    private static int X;//棋盘列数
    private static int Y;//棋盘行数
    //创建一个数组，标记棋盘的各个位置是否被访问过
    private  static  boolean visited[];
    //使用一个属性，标记是否棋盘的所有位置都被访问
    private static boolean finished;//true表示成功

    public static void main(String[] args) {
        //测试骑士周游算法
        X=8;
        Y=8;
        //马的初始位置
        int row=1;
        int column=1;
        //创建棋盘
        int[][] chessboard=new int[Y][X];
        visited=new boolean[X*Y];
        System.out.println("骑士周游问题开始：");
        //测试耗时
        long start=System.currentTimeMillis();
        traversalChessBoard(chessboard,row-1,column-1,1);
        long end=System.currentTimeMillis();
        System.out.println("共耗时:"+(end-start)+"毫秒。");
        //输出棋盘最后情况
        for (int[] rows:chessboard){
            for (int step:rows){
                System.out.print(step+"\t");
            }
            System.out.println();
        }

    }

    /**
     * 完成骑士周游问题
     * @param chessboard 棋盘
     * @param row 马当前位置的行
     * @param column 马当前位置的列
     * @param step 第几步，初始为1
     */
    public  static  void traversalChessBoard(int[][] chessboard,int row,int column,int step){
        chessboard[row][column]=step;
        visited[row*X+column]=true; //标记该位置已经访问
        //获取当前位置可以走的下一个位置的集合
        ArrayList<Point> ps=next(new Point(column,row));
        //优化，对ps每个元素下一步可走个数进行非递减排序
        sort(ps);
        //遍历ps
        while(!ps.isEmpty()){
            Point p= ps.remove(0);//取出下一个可以走的位置
            //判断该点是否已经访问过
            if(!visited[p.y*X+p.x]){
                //说明还未访问
                traversalChessBoard(chessboard,p.y,p.x,step+1);
            }
        }
        //判断马儿是否完成任务
        //未完成则棋盘置零
        if(step<X*Y&&!finished){
            chessboard[row][column]=0;
            visited[row*X+column]=false;
        }else{
            finished=true;
        }

    }

    /**
     * 根据当前位置（Point对象）计算马儿还能走哪些位置，并放入到一个集合中(ArrayList)，最多有八个位置
     * @param curPoint
     * @return
     */
    public static ArrayList<Point> next(Point curPoint){
        //创建一个ArrayList
        ArrayList<Point> ps=new ArrayList<>();
        //创建一个Point
        Point p1=new Point();
        //判断各个位置
        if((p1.x=curPoint.x-2)>=0&&(p1.y=curPoint.y-1)>=0){
            ps.add(new Point(p1));
        }
        if((p1.x=curPoint.x-1)>=0&&(p1.y=curPoint.y-2)>=0){
            ps.add(new Point(p1));
        }
        if((p1.x=curPoint.x+1)<X&&(p1.y=curPoint.y-2)>=0){
            ps.add(new Point(p1));
        }
        if((p1.x=curPoint.x+2)<X&&(p1.y=curPoint.y-1)>=0){
            ps.add(new Point(p1));
        }
        if((p1.x=curPoint.x+2)<X&&(p1.y=curPoint.y+1)<Y){
            ps.add(new Point(p1));
        }
        if((p1.x=curPoint.x+1)<X&&(p1.y=curPoint.y+2)<Y){
            ps.add(new Point(p1));
        }
        if((p1.x=curPoint.x-1)>=0&&(p1.y=curPoint.y+2)<Y){
            ps.add(new Point(p1));
        }
        if((p1.x=curPoint.x-2)>=0&&(p1.y=curPoint.y+1)<Y){
            ps.add(new Point(p1));
        }
        return ps;
    }

    //根据当前这一步的所有下一步的选择位置，进行非递减排序
    public static void sort(ArrayList<Point> ps){
        ps.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                return next(o1).size()-next(o2).size();
            }
        });
    }


}
